/**
 * 
 */
package leetCode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhong
 *
 */
public class EscapeTheGhosts {
	int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
	final int max = 10000;

	public boolean escapeGhosts(int[][] ghosts, int[] target) {
		int pac = Math.abs(target[0]) + Math.abs(target[1]);
		for (int[] gh : ghosts) {
			int dis = Math.abs(target[0] - gh[0]) + Math.abs(target[1] - gh[1]);
			if (dis <= pac) {// 如果存在ghost先到，则不能成功
				return false;
			}
		}
		return true;
	}

	public boolean escapeGhostsxx(int cur, HashSet<Integer> ghosts, int target) {
		boolean ghostsWalk = true;
		Queue<Integer> pos = new LinkedList<>();
		pos.add(0);
		while (!pos.isEmpty()) {
			// 任意一个ghost向任意一个方向移动，或者不动，能否碰到当前位置的下一个位置
			if (ghostsWalk) {
				int beforesize = ghosts.size();
				for (Integer i : ghosts) {
					int x = i / max;
					int y = i % max;
					for (int[] d : dir) {
						int newx = x + d[0];
						int newy = x + d[1];
						if (Math.abs(newx) <= max && Math.abs(newy) <= max) {// 合法坐标
							ghosts.add(max * newx + newy);
						}
					}
				}
				if (ghosts.size() == beforesize) {// 无需继续
					ghostsWalk = false;
				}
			}
			if (ghosts.contains(target)) {// 敌人呆在目标点，就不能到达
				return false;
			}
			// pacman上一层所有位置走到下一层

		}
		return false;

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
